COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	let1[f82,jmc]		A call-by-need let macro
C00008 00003	 examples
C00012 ENDMK
C⊗;
let1[f82,jmc]		A call-by-need let macro

	Let  exp{exp1}  be a pure Lisp expression that contains
exp1  as a subexpression occurring several times.  We can ensure
that  exp1  is computed at most once by writing

	((lambda (x) exp{x}) exp1)

or

(let ((x exp1)) exp{x}).

However, this may not be optimal because  exp1  may be part of a
conditional expression and may not have to be computed at all if
the propositions don't require it.

	The conventional modern solution to this problem is to
package  exp1  into an object or actor or whatever the formalism
calls for.  When it is first called, it modifies itself, so that
it gives the answer right away at any subsequent calls.  We may
also use a call-by-need interpreter and then lambda is ok.  All of
these solutions involves local state, and this is problematical
for the theory.  Another possibility is to have the program
explicitly pass the value of exp1 along to the next use.  This
makes for obscure programs.  We are about to propose a third
solution, and the term project is to implement it.

	We need the notion of an inevitable subexpression of
an expression.  We say that  exp1  is inevitable in  exp  if
exp1  is always evaluated in the course of evaluating  exp.
In this case, there is no problem; the above-mentioned  lambda
expression or  let  expression will work.  Suppose  exp1  is
not inevitable.  Then it is because  exp1  occurs in a conditional
expression within  exp,  not all branches of which contain it.

Case 1.  exp  is a conditional expression of the form

	if p then exp2 else exp3,

and  exp1  occurs only in  exp2  and is inevitable in  exp2, so
we write  exp2  as  exp2{exp1}.  This is easily handled; we replace
exp by

	if p then [λx.exp2{x}][exp1] else exp3

or by the corresponding expression using  let.
If  exp1  occurs only in  exp2  but is not inevitable in  exp2,
then we must dig deeper, i.e. the replacement by a λ-expression
will occur a a deeper level.  If  exp  itself isn't a conditional
expression but the conditional expression is inevitable in  exp,
the replacement occurs as before.  If  exp1  is inevitable in both
exp2  and  exp3  or is inevitable in  p,  then it is inevitable in
the whole conditional expression, which can then be rewritten

	[λx.if p{x} then exp2{x} else exp3{x}][exp1].

It may happen that  exp1  occurs in both  exp2  and  exp3  but
isn't inevitable in both.  In this case both have to be transformed.

	The interesting case is when  exp1  occurs in  p  but is
not inevitable in  p  and also occurs in  exp2  or exp3.
Then  exp1  may have to be evaluated in the course of computing  p,
and the value may have to be saved for the subsequent computations.
This can only happen if  p  itelf contains a conditional expression.
Using the distributive law for conditional expressions and functions,
this internal conditional expression can come to the top of  p,
so that we now have something of the form

	if (if q then r else s) then exp1 else exp2.

where  exp1  occur in  q,  r,  or  s  with the same subcases as before
including this case.  We then use one of the rules for transforming
conditional expressions to get

	if q then (if r then exp2 else exp3) else (if s then exp2 else exp3)

which reduces the complexity of the problem, i.e. the only interesting
case is when  exp1  occurs in  q  but not inevitably.  After some
number of transformations, we are back at an easy case.

	All this can be done automatically by a macro we shall call
let-by-need.  We write

	let-by-need[[x←exp1] exp{x}]

or in internal notation

(let-by-need ((x exp1)) exp{x}),

and the  let-by-need  macro performs all the required expansions.


Problem due December 8

Write the let-by-need macro and test it.
;;; examples

frmak x ← <x>
frnull x ← n x
frcar x ← if at a x then a x else a gopher a x
frcdr x ← if at a x then nil else <d gopher a x>

or

frmak x ← if at x then <x> else <gopher x>
frnull x ← n x
frcar x ← if at a x then a x else aa x
frcdr x ← if at a x then nil <gopher da x>

samefringe[x,y] ← same1[frmak x,frmak y]
same1[u,v] ← frnull u ∧ frnull v
		∨ ¬frnull u ∧ ¬frnull v ∧ frcar u eq frcar v ∧ same1[frcdr u,frcdr v]

(defun frmak (x) (list x))

(defun frnull (x) (null x))

(defun frcar (x) (if (atom (car x)) (car x) (car (gopher (car x)))))

(defun frcdr (x) (if (atom (car x)) nil (list (cdr (gopher (car x))))))

(defun frmak1 (x) (if (atom x) (list x) (list (gopher x))))

(defun frnull1 (x) (null x))

(defun frcar1 (x) (if (atom (car x)) (car x) (caar x)))

(defun frcdr1 (x) (if (atom (car x))
		      nil
		      (if (atom (cdar x))
			  (list (cdar x))
			  (list (gopher (cdar x))))))

(defun gopher (xx) (if (atom (car xx))
		       xx
		       (gopher (cons (caar xx) (cons (cdar xx) (cdr xx))))))

(defun samefringe (x y) (same (frmak x) (frmak y)))

(defun same (u v)
       (or (and (frnull u)
		(frnull v))
	   (and (not (frnull u))
		(not (frnull v))
		(eq (frcar u) (frcar v))
		(same (frcdr u) (frcdr v)))))

(defun samefringe1 (x y) (same1 (frmak1 x) (frmak1 y)))

(defun same1 (u v)
       (or (and (frnull1 u)
		(frnull1 v))
	   (and (not (frnull1 u))
		(not (frnull1 v))
		(eq (frcar1 u) (frcar1 v))
		(same1 (frcdr1 u) (frcdr1 v)))))

(defun gopher2 (x)
       (if (or (atom x) (atom (car x)))
	   x
	   (gopher2 (cons (caar x) (cons (cdar x) (cdr x))))))

(defun frmak2 (x) (gopher2 x))

(defun frnull2 (x) (equal x '((nil))))

(defun frcar2 (x) (if (atom x) x (car x)))

(defun frcdr2 (x) (if (atom x) '((nil)) (gopher2 (cdr x))))

(defun samefringe2 (x y) (same2 (frmak2 x) (frmak2 y)))

(defun same2 (u v)
       (or (and (frnull2 u)
		(frnull2 v))
	   (and (not (frnull2 u))
		(not (frnull2 v))
		(eq (frcar2 u) (frcar2 v))
		(same2 (frcdr2 u) (frcdr2 v)))))